对于非常大的整数,Python中整数比较的时间复杂度是多少？例如,如果我们使用2个函数计算1000的阶乘,那么检查相等性,是O(1)？

Tim Peters.. 6

没有一个简单的答案,但答案显而易见;-)

也就是说,如果两个整数实际上是相等的,那么在不比较所有位的情况下就不可能知道.因此,在相等的情况下,所需的时间与位数成比例(与log(abs(N))if N是比较之一成比例).

如果它们实际上不相等,则有几种情况,都与实施内部相关.长整数被存储为2位幂的"数字"向量.如果载体不具有相同的长度,则该整数不相等,并且其花费一定的时间.

但如果它们具有相同的长度,那么必须比较"数字"直到找到第一个(如果有的话)不匹配对.这需要与需要比较的位数成比例的时间.

然后使上述所有内容复杂化以考虑可能的符号混合.

1> Tim Peters..：

没有一个简单的答案,但答案显而易见;-)

也就是说,如果两个整数实际上是相等的,那么在不比较所有位的情况下就不可能知道.因此,在相等的情况下,所需的时间与位数成比例(与log(abs(N))if N是比较之一成比例).

如果它们实际上不相等,则有几种情况,都与实施内部相关.长整数被存储为2位幂的"数字"向量.如果载体不具有相同的长度,则该整数不相等,并且其花费一定的时间.

但如果它们具有相同的长度,那么必须比较"数字"直到找到第一个(如果有的话)不匹配对.这需要与需要比较的位数成比例的时间.

然后使上述所有内容复杂化以考虑可能的符号混合.